package algorithm.niuke;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * 树的相关问题
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-05-13
 */
public class TreeTest {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        TreeNode subRoot = new TreeNode(1);

        TreeTest tt = new TreeTest();
        boolean isSubTree = tt.hasSubtree(root, subRoot);
        System.out.println(isSubTree);

        tt.mirror(root);
        System.out.println(root);


        ArrayList<ArrayList<Integer>> path = tt.findPath(null, 1);
        System.out.println(path);
    }

    /**
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
     *
     * @param root1 树A
     * @param root2 树B
     * @return B是否是A的子树 是返回true，否则返回false
     */
    private boolean hasSubtree(TreeNode root1, TreeNode root2) {

        boolean isSubTree = false;

        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                isSubTree = judgeSubTree(root1, root2);
            }
            if (!isSubTree) {
                isSubTree = hasSubtree(root1.left, root2);
            }
            if (!isSubTree) {
                isSubTree = hasSubtree(root1.right, root2);
            }
        }
        return isSubTree;

    }

    private boolean judgeSubTree(TreeNode root, TreeNode subRoot) {

        if (root == null && subRoot != null) {
            return false;
        }
        if (subRoot == null) {
            return true;
        }
        if (root.val != subRoot.val) {
            return false;
        }
        return judgeSubTree(root.left, subRoot.left) && judgeSubTree(root.right, subRoot.right);
    }


    /**
     * 操作给定的二叉树，将其变换为源二叉树的镜像。（左右子树交换，根结点不变）
     *
     * @param root 一颗树的根结点
     */
    private void mirror(TreeNode root) {

        // 判断传过来的树是否没null或者没有左右子树
        boolean hasSubTree = ((root == null) || (root.left == null && root.right == null));
        // 如果上面条件成立直接返回
        if (hasSubTree) {
            return;
        }

        // 来到这里树至少有一个子结点，交换位置
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 如果有左子树，递归去交换
        if (root.left != null) {
            mirror(root.left);
        }
        // 如果有右子树，递归交换
        if (root.right != null) {
            mirror(root.right);
        }


    }


    /**
     * 打印出二叉树中结点值的和为输入整数的所有路径
     *
     * @param root   根结点
     * @param target 目标数
     * @return 所有路径集合
     */
    public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {

        ArrayList<ArrayList<Integer>> pathList = new ArrayList<>(10);
        ArrayList<Integer> path = new ArrayList<>(10);

        helper(root, target, path, pathList);

        // 排序，把短的路径放前面
        pathList.sort(Comparator.comparingInt(ArrayList::size));
        return pathList;
    }

    private void helper(TreeNode root, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> pathList) {
        if (root == null) {
            return;
        }
        int val = root.val;
        path.add(val);
        if (target == val && root.left == null && root.right == null) {
            pathList.add(new ArrayList<>(path));
        } else {
            helper(root.left, target - val, path, pathList);
            helper(root.right, target - val, path, pathList);
        }

        path.remove(path.size() - 1);
    }


    /**
     * 将该二叉搜索树转换成一个排序的双向链表
     *
     * @param pRootOfTree 二叉树
     * @return 排序的双向链表
     */
    private TreeNode convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        if (pRootOfTree.left == null && pRootOfTree.right == null) {
            return pRootOfTree;
        }

        // 1.将左子树构造成双链表，并返回链表头节点c
        TreeNode left = convert(pRootOfTree.left);
        TreeNode p = left;
        // 2.定位至左子树双链表最后一个节点
        while (p != null && p.right != null) {
            p = p.right;
        }
        // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
        if (left != null) {
            p.right = pRootOfTree;
            pRootOfTree.left = p;
        }
        // 4.将右子树构造成双链表，并返回链表头节点
        TreeNode right = convert(pRootOfTree.right);
        // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
        if (right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left != null ? left : pRootOfTree;
    }

}
